package com.mamingchao.issue.oneDirectionStack;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingDeque;

class OneDirection {

    public static void main(String[] args) {
        final int  windowWidth = 3;
        
        int[] arr ={5,4,3,6,2,1,7,9,8};
        // int[] result = getMaxValueArray(arr, windowWidth);
        int[][] result = getLeftRightLargerIndex(arr);
        System.out.println(Arrays.toString(result));
    }



    /**
     * 
     * @param arr
     * @return 
     */
    private static int[] getMaxValueArray(int[]  arr, final int subArrayWindowWidth){
        LinkedBlockingDeque<Integer> oneDirectionDeque = new LinkedBlockingDeque<Integer>();
        int[] result = new int[arr.length - subArrayWindowWidth + 1];
        int L = 0;
        int R = 0;

        while (R < arr.length) {
            if (R >=  L + subArrayWindowWidth) {
                shiftRightByOne(-1, L++, R, arr, oneDirectionDeque);
            }
            
            shiftRightByOne(1, L, R++, arr, oneDirectionDeque);
            result[L] = getMaxValueInSubArray(oneDirectionDeque);
        }
        
        return result;
    }

    /**
     * 获取子数组的最大值
     * @param oneDirectionDeque
     * @return 子数组的最大值
     */
    private static int getMaxValueInSubArray( LinkedBlockingDeque<Integer> oneDirectionDeque){

        if (org.springframework.util.CollectionUtils.isEmpty(oneDirectionDeque)) {
            return 0;
        }
        return oneDirectionDeque.getFirst();
    }

    /**
     * 滑动窗口左边界和右边界向右移动一位的统一处理方法
     * 双端单调性队列
     * @param direction 方向； L:-1, R：1
     * @param L 移动后的左边界元素 index
     * @param R 移动后的右边界元素 index
     * @param arr 原始数组
     * @param oneDirectionDeque 单调双端队列
     * @return
     */
    private static void shiftRightByOne(int direction, int L, int R, int[] arr, LinkedBlockingDeque<Integer> oneDirectionDeque){

        if(direction == -1){
            // 左边界右移一位
            int left = oneDirectionDeque.getFirst();
            if(left == arr[L]){
                oneDirectionDeque.removeFirst();
            }
        }else{
            // 右边界右移一位
            int right = arr[R];
            while(oneDirectionDeque.size()>0 && right >= oneDirectionDeque.getLast()){
                oneDirectionDeque.removeLast();
            }
            oneDirectionDeque.addLast(right);
        }
    }

    /**
     * 基于单调栈，实现获取每个数的最大左边数和右边数的index 数组
     * @param arr 原始数组
     * @return 返回每个
     */
private static int[][] getLeftRightLargerIndex(int[] arr){

    Stack<ArrayDeque<Integer>> oneDirectionStack = new Stack<>();
    int[][] result = new int[arr.length][2];

    for (int i = 0; i < result.length; i++) {
        int lastIndex = -1;
        int lastValue = Integer.MIN_VALUE;

        if (!oneDirectionStack.isEmpty()) {
            lastIndex = oneDirectionStack.peek().getLast();
            lastValue = arr[lastIndex];
        }

        // 如果栈为空, 或者  上一个栈元素大于当前元素，则将当前元素入栈
        if (oneDirectionStack.isEmpty() || lastValue> arr[i]) {
            ArrayDeque<Integer> curItemIndexs = new ArrayDeque<>();
            curItemIndexs.add(i);
            oneDirectionStack.push(curItemIndexs);
        } else if (lastValue == arr[i]) { // 如果上一个栈元素等于当前元素，则 当前元素存放到上一栈元素的索引列表中
            ArrayDeque<Integer> curItemIndexs = oneDirectionStack.peek();
            curItemIndexs.add(i);
        } else { // 上一个栈元素小于当前元素，则将当前元素入栈
            while (lastValue < arr[i]) {
                lastIndex = oneDirectionStack.peek().getLast();
                lastValue = arr[lastIndex];

                ArrayDeque<Integer> curItemIndexs = oneDirectionStack.pop();
                for (Integer index : curItemIndexs) {
                    result[index][0] = oneDirectionStack.isEmpty() ? -1 : lastIndex;
                    result[index][1] = i;
                }
            }

            ArrayDeque<Integer> curItemIndexs = new ArrayDeque<>();
            curItemIndexs.add(i);
            oneDirectionStack.push(curItemIndexs);
        }
    }


    while (!oneDirectionStack.isEmpty()) {
        ArrayDeque<Integer> curItemIndexs = oneDirectionStack.pop();
        for (Integer index : curItemIndexs) {
            result[index][0] = oneDirectionStack.isEmpty() ? -1 : oneDirectionStack.peek().getLast();
            result[index][1] = -1;
        }
    }
    return result;
}
    
}